/*
* 树结构的基本概念：
*   一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（顶部第一个节点除外）以及零个或多个子节点，节点内部存储数据。
*   元素节点类似于数组中的下标，节点内部存储的数据类似于数组下标所对应的值。
*   位于最上面树顶部的节点叫做根节点，它没有父节点。树中的每个元素都叫做节点，节点分为内部节点和外部节点。
*   至少有一个子节点的节点称为内部节点。没有子元素的节点称为外部节点或叶节点（就像树的叶子）。
*   一个节点可以有祖先和后代（父节点，祖父节点，曾祖父节点。子节点，孙子节点，曾孙节点）。
*   子树，子树由某节点和它的所有后代节点构成（即从该节点一直到它所有叶节点的范围）。
*   节点的一个属性是深度，节点的深度取决于它祖先节点的数量，不包括该节点自身。它往上有多少祖先节点，它就有多深。
*   树的高度取决于所有节点中深度的最大值。一棵树也可以被分解为层级。根节点在第0层，根节点的子节点在第1层，以此类推。
*
* 树结构的基本概念之二叉树：
*   二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。这个定义有助于我们写出更高效的在树中插入、查找和删除节点的算法。
*   二叉搜索树（BST）是二叉树中的一种，但是只允许在左侧子节点存储比父节点小的值，在右侧子节点存储比父节点大的值。
*
* 树结构的技术实现之先、中、后序遍历（面试可能会需要手写代码！！！代码一模一样，就是cb行位置前中后不同）
*   遍历一棵树是指访问树的每个节点并对它们进行某种操作的过程。
*   访问树的所有节点有三种方式：中序遍历（排序）、先序遍历（类似文档结构）、后序遍历（查询整个文档的大小）
*   1.中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。
*   2.先序遍历是以祖先节点优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。
*     先序遍历与中序遍历的不同之处在于，先序遍历会先访问节点本身，然后再访问它的左侧子节点，最后是右侧子节点。
*   3.后序遍历是优先访问节点的后代节点，再访问节点本身。后序遍历的一种应用场景是计算一个目录及其子目录中所有文件所占空间的大小。
*     后序遍历是会先访问节点的左侧子节点，然后是节点的右侧子节点，最后是父节点本身。
*
* */

//树中每个存储数据的地方叫元素节点，所以要创建一个节点的类
class Node{
    constructor(key){ //这里的key不像是栈或者队列里面的索引，树的key直接对应的就是节点所存储的数据值
        this.key = key //存储节点值
        this.left = null //索引，指向左侧子节点，就像双向链表，链表是上下结构（指针域指向上和下），树是左右结构（指向左和右）
        this.right = null //索引，指向右侧子节点
    }
}

//二叉搜索树类
class BinarySearchTree{
    constructor(){
        this.root = null //二叉树的根节点，默认值为null，初始化
    }

    insert(key){ //往二叉树里面插入新的值
        if(!this.root){ //如果根节点没有值，那么就插到二叉树的根节点中
            this.root = new Node(key)
        }else{ //如果根节点已经有了值，做判断，比较插入的子节点的值与父节点的值得大小，来决定是左侧子节点还是右侧子节点
            //调用往某个节点插入值的方法
            this.insertNode(this.root,key) //this.root是因为要每次插入新值的时候，要从根节点开始做比较大小的判断并插入值
        }
    }

    insertNode(node,key){ //往某个节点插入一个值，node表示父节点，key表示子节点的值，子节点的值要和父节点的值比较后决定左右侧
        //这么写的原因是为了在已经有了大量数据的时候，能够递归地调用
        if(key < node.key){ //如果待插入的值 比 父节点的值小，插左边
            //还要细分，如果该父节点的左边已经有了一个子节点（因为不可能每次都是插入根节点的子节点，万一有很多层），那么就要判断
            if(node.left){ //该父节点左侧已有子节点，待插入的值 就要成为 该子节点 的 子节点（不确定有多少层，所以要递归）
                this.insertNode(node.left,key) //递归调用往某个节点插入值的方法，这次是左侧子节点的值与待插入值比较大小
            }else{ //如果该父节点左侧没有子节点，直接插入成为该父节点的子节点
                node.left = new Node(key)
            }
        }else{ //大于或是等于插右边同样右侧子节点也要进行递归判断
            if(node.right){ //该父节点右侧已有子节点，待插入的值 就要成为 该子节点 的 子节点（不确定有多少层，所以要递归）
                this.insertNode(node.right,key) //递归调用往某个节点插入值的方法，这次是右侧子节点的值与待插入值比较大小
            }else{ //如果该父节点右侧没有子节点，直接插入成为该父节点的子节点
                node.right = new Node(key)
            }
        }
    }

    min(){ //查询整个二叉树的最小值，同样需要一个递归方法，因为无法得知哪个节点才是最小值
        return this.minNode(this.root) //返回 从根节点开始递归判断查找最小值的函数方法 的 返回值
    }
    //注意区分min方法和minNode方法的区别，一个是查找整个树的最小值，一个是从某个节点开始往下的最小值（不一定是整个树的最小值）
    minNode(node){ //从某个指定的节点开始 递归地判断查找最小值方法，node表示传入的节点
        let current = node //将每一次当前传入的节点保存在变量中
        while(current && current.left){ //当 当前节点存在值 并且 当前节点的左侧子节点也存在值时，说明还有更小的值
            current = current.left //就将左侧子节点的变成当前节点，继续进行循环比较
        }
        //否则直接进行返回，左侧没有子节点就表明当前节点就是最小值所在节点
        return current
    }

    max(){ //查询整个二叉树的最大值，同样需要一个递归方法，因为无法得知哪个节点才是最小值
        return this.maxNode(this.root) //返回 从根节点开始递归判断查找最小值的函数方法 的 返回值
    }
    //注意区分max方法和maxNode方法的区别，一个是查找整个树的最大值，一个是从某个节点开始往下的最大值（不一定是整个树的最大值）
    maxNode(node){ //从某个指定的节点开始 递归地判断查找最大值方法，node表示传入的节点
        let current = node //将每一次当前传入的节点保存在变量中
        while(current && current.right){ //当 当前节点存在值 并且 当前节点的右侧子节点也存在值时，说明还有更大的值
            current = current.right //就将右侧子节点的变成当前节点，继续进行循环比较
        }
        //否则直接进行返回，右侧没有子节点就表明当前节点就是最大值所在节点
        return current
    }

    //中序遍历
    inOrderTraverse(cb){ //接收一个回调函数，中序遍历排序
        this.inOrderTraverseNode(this.root,cb) //从根节点开始中序遍历排序
    }

    inOrderTraverseNode(node,cb){ //中序遍历递归方法
        if(node){ //当该节点存在的时候才做遍历操作
            this.inOrderTraverseNode(node.left,cb)
            //一直往左边子节点寻找，如果下面还有左侧子节点又会进入这一层的递归方法，但是不会运行到下一行cb()，
            //因为当前停留在这一层并进入这一层递归里面了（这就是不会立马执行cb的原因），如果还有左侧子节点，又是重复这个操作
            //直到没有下一个左侧子节点才会跳出当前层的递归，回到上一层，进行下一行cb()操作
            cb(node.key) //直到没有左侧子节点就把现在停留在节点的值放到回调函数进行操作
            this.inOrderTraverseNode(node.right,cb) //同理，依旧要判断这个右侧子节点的下面还有没有左侧子节点，如果有，进入当前层递归
        }
    }

    //先序遍历
    preOrderTraverse(cb){ //接收一个回调函数，先序遍历数据的结构
        this.preOrderTraverseNode(this.root,cb) //从根节点开始先序遍历
    }

    preOrderTraverseNode(node,cb){ //先序遍历递归方法
        if(node){ //当该节点存在的时候才做遍历操作
            cb(node.key) //把遍历到的值放到回调函数进行操作
            this.preOrderTraverseNode(node.left,cb)
            //一直往左边子节点寻找，如果下面还有左侧子节点又会进入这一层的递归方法，但是不会运行到下一行
            //因为当前停留在这一层并进入这一层递归里面了（这就是不会立马执行cb的原因），如果还有左侧子节点，又是重复这个操作
            //直到没有下一个左侧子节点才会跳出当前层的递归，回到上一层，进行下一行操作
            this.preOrderTraverseNode(node.right,cb) //同理，依旧要判断这个右侧子节点的下面还有没有子节点，如果有，进入当前层递归
        }
    }

    //后序遍历
    postOrderTraverse(cb){ //接收一个回调函数，后序遍历
        this.postOrderTraverseNode(this.root,cb) //从根节点开始后序遍历排序
    }

    postOrderTraverseNode(node,cb){ //后序遍历递归方法
        if(node){ //当该节点存在的时候才做遍历操作
            this.postOrderTraverseNode(node.left,cb)
            //一直往左边子节点寻找，如果下面还有左侧子节点又会进入这一层的递归方法，但是不会运行到下一行，
            //因为当前停留在这一层并进入这一层递归里面了（这就是不会立马执行下一行的原因），如果还有左侧子节点，又是重复这个操作
            //直到没有下一个左侧子节点才会跳出当前层的递归，回到上一层，进行下一行操作
            this.postOrderTraverseNode(node.right,cb) //同理，依旧要判断这个右侧子节点的下面还有没有左侧子节点，如果有，进入当前层递归
            cb(node.key) //直到左侧子节点之下没有右侧子节点就把现在停留在节点的值放到回调函数进行操作
        }
    }

    //查找功能
    searchKey(key){
        return this.searchNode(this.root,key)
    }

    searchNode(node,key){ //递归方法
        //先判断树里面有没有东西
        if(node){ //树中必须有节点才能进行搜索
            //再判断值的大小，决定从哪边搜
            if(key < node.key){ //如果传入的值比当前节点的值小，继续搜索左侧子节点
                return this.searchNode(node.left,key)
            }else if(key > node.key){ //如果传入的值比当前节点的值大，继续搜索右侧子节点
                return this.searchNode(node.right,key)
            }else{ //既不是大于也不是小于那就是搜到了
                return true
            }
        }else{ //如果节点都不存在那就不用搜了
            return false
        }
    }

    //删除功能
    removeKey(key){
        this.root = this.removeNode(this.root,key)
    }

    removeNode(node,key){
        if(node){ //树里面有节点存在才能删
            if(key < node.key){ //从左侧开始搜
                node.left = this.removeNode(node.left,key)
                return node //返回拼接后的节点
            }else if(key > node.key){ //从右侧开始搜
                node.right = this.removeNode(node.right,key)
                return node //返回拼接后的节点
            }else{ //找到了要删除的对象
                //第一种情况：待删除的节点下面左右两侧都有子节点
                if(node.left && node.right){
                    console.log("替换前节点",node)
                    console.log("替换前右侧子节点",node.right)

                    let target = this.minNode(node.right) //将待删除节点的右侧子节点的所有子节点中最小的子节点找出来，即最小孙子节点
                    node.key = target.key //最小孙子节点替补到被删除节点的位置上
                    node.right = this.removeNode(node.right,key) //把那个找来做替补的最小孙子节点从原来的孙子位置上删掉

                    console.log("替换后节点",node)
                    console.log("替换后右侧子节点",node.right)

                    return node
                }

                //第二种情况：待删除节点左侧或者右侧有子节点
                if(node.left || node.right){
                    if(node.left){ //如果待删除节点左侧有子节点，左侧子节点替代被删除节点
                        node = node.left
                    }
                    if(node.right){ //同理
                        node = node.right
                    }
                    return node //返回替代后的节点
                }

                //第三种情况：待删除节点就是一个叶节点
                node = null
                return node
            }
        }else{
            return null
        }
    }

    //修改功能
    updateKey(key,key1){
        return this.updateNode(this.root,key,kye1)
    }

    updateNode(node,key,key1){ //递归方法
        //先判断树里面有没有东西
        if(node){ //树中必须有节点才能进行搜索
            //再判断值的大小，决定从哪边搜
            if(key < node.key){ //如果传入的值比当前节点的值小，继续搜索左侧子节点
                return this.updateNode(node.left,key,key1)
            }else if(key > node.key){ //如果传入的值比当前节点的值大，继续搜索右侧子节点
                return this.updateNode(node.right,key,key1)
            }else{ //既不是大于也不是小于那就是搜到了
                node.key = key1
                return true
            }
        }else{ //如果节点都不存在那就不用搜了
            return false
        }
    }
}

let treeData = new BinarySearchTree() //实例化对象
treeData.insert(10)
treeData.insert(4)
treeData.insert(16)
treeData.insert(3)
treeData.insert(8)
treeData.insert(13)
treeData.insert(20)
//treeData.insert(11)
//treeData.insert(1)
//treeData.insert(21)
//treeData.insert(3241)
//treeData.insert(10)
//treeData.insert(8)
//treeData.insert(4)
//treeData.insert(3)
//treeData.insert(90)
//treeData.insert(19)
//treeData.insert(14)